#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 110;
const int mod = 2009;

int m;

struct mat{
	int arr[N][N];
	const int * operator [](int x)const{return arr[x];}
	int * operator [](int x){return arr[x];}
	mat(){for(int i = 0;i < m;i++) for(int j = 0;j < m;j++) arr[i][j] = 0;}
	friend mat operator * (mat a,mat b){
		mat c;
		for(int i = 0;i < m;i++)
			for(int j = 0;j < m;j++)
				for(int k = 0;k < m;k++)
					c[i][k] = (c[i][k] + a[i][j] * b[j][k] % mod) % mod;
		return c;
	}
}ans,f;

int a[N][N],n,t;
char s[N];

int id(int x,int d){return x + d * n;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in;t = in; m = n * 10; ans = mat(); f = mat();
	if(t == 0) return printf("%d\n",n == 1),0;
	for(int i = 1;i <= n;i++){
		scanf("%s",s + 1);
		for(int j = 1;j <= 8;j++) f[id(i,j)][id(i,j-1)] = 1;
		for(int j = 1;j <= n;j++){
			if(s[j] == '0') continue;
			int d = s[j] - '0'; f[id(i,0)][id(j,d-1)] = 1;
		}
	}
	ans = f;
	for(--t;t;f = f * f,t >>= 1) if(t & 1) ans = ans * f;
	printf("%d\n",ans[id(1,0)][id(n,0)]);
	return 0;
}

